nLab tree

Redirected from "binary trees".
Contents

Contents

Idea

A tree is a connected graph without cycles. Some notions of tree (such as planar tree) consider extra structure or properties as well, but the baseline notion is tree as acyclic connected graph.

Trees are fundamental combinatorial objects which appear in a wide variety of guises. Some are given below.

Definitions

As undirected graphs

Recall that an undirected graph GG consists of a set VV of vertices and a set EE of unordered pairs of vertices. A path in GG is a finite sequence of vertices x 0,,x nx_0, \ldots, x_n such that each pair x ix i+1x_i x_{i+1} belongs to EE. If x n=x 0x_n = x_0, then the path is called a cycle. A graph is connected if it is nonempty and if for every distinct pair of vertices x,yx, y, there is a path for which x 0=xx_0 = x and x n=yx_n = y. A graph is acyclic if the only cycles are paths

x 0,,x n1,x n,x n1,,x 0x_0, \ldots, x_{n-1}, x_n, x_{n-1}, \ldots, x_0

where steps are retraced; an acyclic graph is also called a forest. A tree is a connected forest.

Each forest is a disjoint sum (a coproduct in the category of graphs) of trees. Removal of a vertex of a tree (and any edges incident to it) results in a forest.

Not all authors include nonemptiness as part of the notion of connectedness. See connected space for commentary on this. Forests on the other hand may be empty.

As spaces

A topological tree is a 1-dimensional CW-complex which is contractible, i.e., homotopy equivalent to a point.

In this language, a topological graph is simply a 1-dimensional CW-complex; more precisely, we mean a CW-presentation and not merely a space that can be so presented. A topological forest is then a 1-dimensional CW-complex with vanishing first homology group with integral coefficients, and a tree is a connected forest.

For finite graphs GG as CW-complexes, one has the useful Euler formula:

h 0h 1=c 0c 1h_0 - h_1 = c_0 - c_1

where c ic_i is the number of ii-cells and h ih_i is the rank of the homology group H i(G;)H_i(G; \mathbb{Z}). This gives a useful criterion for a graph to be a tree: that it be connected (h 0=1h_0 = 1) and that the number of vertices c 0c_0 be 1 greater than the number of edges c 1c_1.

As digraphs

A rooted tree is a directed graph (or quiver) GG such that the free category generated by GG has a terminal object, called the root of GG. (Thus for every vertex xx in GG there is exactly one directed path from xx to the root. It follows easily that the free category is a poset. There is no significant change in content if “terminal” here is replaced by “initial”; we can distinguish the conventions by a tree directed towards the root rather than away from the root.)

A rooted forest is a coproduct of rooted trees, and again we have the fundamental fact that there is a natural equivalence of categories

TreeForestTree \overset{\to}{\leftarrow} Forest

which in one direction is the functor which sends a tree to the forest which results by excising the root and all edges incident to it, and in the other sends a forest to the tree gotten by adjoining a new root and joining the roots of the forest to that new root by new edges.

This equivalence can be exploited to relate the exponential generating function for finite rooted trees to the Lambert W-function (q.v.).

A tree in the form of an undirected graph together with a chosen vertex can be regarded as a rooted tree in digraph form (with root the chosen vertex), by orienting all edges in the direction of paths going to the root. The category of rooted trees has very nice categorical properties not shared by the category of unrooted trees; see the following section.

As ordered sets

In order theory, a tree is described by a partial order with the added property that it is downward well ordered. Let SS be a partially ordered set, then SS is a tree when for each xSx \in S the downward closure or history x ={yyx}x^- = \{ y \mid y \leq x \} is a well ordered subset of SS. If instead of a well-order we find that x x^- is only totally ordered (meaning that points in the tree do not have a distinguished successor) we say that SS is prefix ordered.

As functors

Let \mathbb{N} be the totally ordered set of natural numbers 0120 \leq 1 \leq 2 \leq \ldots, viewed as a category. A rooted forest is a presheaf on \mathbb{N}, i.e., a functor

F: opSetF: \mathbb{N}^{op} \to Set

to “the” category of sets. A rooted tree is a forest for which F(0)F(0) is terminal (a point).

In this case, we get from a tree as functor FF to a tree as digraph by passing to the category of elements El(F)El(F). The vertices of the digraph are the elements, and the edges are those morphisms of El(F)El(F) which map to morphisms i+1ii + 1 \to i in op\mathbb{N}^{op}. Notice that op\mathbb{N}^{op} is itself (the free category on) a tree as digraph, one that is terminal in the category of forests.

In the other direction, starting with a tree as digraph, we define a functor F: opSetF \colon \mathbb{N}^{op} \to Set by letting F(n)F(n) be the set of vertices vv such that the path from vv to the root has nn edges. The map F(n+1)F(n)F(n+1) \to F(n) moves a vertex vF(n+1)v \in F(n+1) to the vertex that is one step closer to the root (along the unique path from vv to the root).

The functor description makes it clear that the category of forests is a (presheaf) topos, indeed a Grothendieck topos; therefore the category of trees, which is equivalent, is also a topos.

If we replace SetSet here by the category of totally ordered sets TosTos, then we may define a planar forest as a functor

F: opTosF: \mathbb{N}^{op} \to Tos

As terminal coalgebra

The category of trees as described in the section immediately above can be described universally in 2-universal terms, as the 2-terminal coalgebra for the endofunctor on CatCat (locally small categories) which takes a category to its small-coproduct cocompletion. See terminal coalgebra for an extended discussion.

As operations

Let F\mathbf{F} denote the free (strict) monoidal category generated by nn-ary operations θ n:x nx\theta_n: x^n \to x, one for each arity n0n \geq 0. A (finite) planar forest with (nn) live leaves is a morphism ϕ:x nx m\phi: x^n \to x^m in F\mathbf{F}; a (finite) planar tree with (nn) live leaves is a morphism ϕ:x nx\phi: x^n \to x.

The previous description is more a theorem than definition, but it points to the recursive construction of trees based on the fundamental equivalence between forests and trees:

  • The identity xxx \to x corresponds to a root considered as a live leaf;

  • Given trees with live leaves f j:x n jxf_j \colon x^{n_j} \to x, where j{1,k}j \in \{1 \ldots, k\}, there is a forest

    f 1f k:x n 1++n k=x n 1x n kxx=x kf_1 \otimes \ldots \otimes f_k \colon x^{n_1 + \ldots + n_k} = x^{n_1} \otimes \ldots \otimes x^{n_k} \to x \otimes \ldots \otimes x = x^k

    whose set of live leaves is the disjoint union of sets of live leaves of the f jf_j.

  • Given a forest with live leaves

    f 1f k:x n 1++n k=x n 1x n kxx=x kf_1 \otimes \ldots \otimes f_k \colon x^{n_1 + \ldots + n_k} = x^{n_1} \otimes \ldots \otimes x^{n_k} \to x \otimes \ldots \otimes x = x^k

    there is a tree

    θ n(f 1f k):x n 1++n kx\theta_n \circ (f_1 \otimes \ldots \otimes f_k) \colon x^{n_1 + \ldots + n_k} \to x

    with the same set of live leaves.

In more straightforward combinatorial language: if a finite planar tree is a functor F:[n] opΔ aF \colon [n]^{op} \to \Delta_a from a finite ordinal to the augmented simplex category, and a leaf is an element without predecessors in the poset of elements of FF, then we can consider as extra structure some subset of the leaves whose elements are designated as live. The principle is that one is permitted to graft roots of trees onto live leaves, but not onto dead ones. (Dead leaves arise by plugging in the constant = 00-ary operation θ 0:I=x 0x\theta_0 \colon I = x^0 \to x.)

Fancier versions of this basic recursive construction may involve “colored trees”, “cherry trees”, and so on, and figure prominently in the theory of operads, especially in the construction of free operads.

In fact, this type of recursivity is at the root (pun perhaps intended) of the cumulative hierarchy conception of sets in a material set theory like ZFC set theory: all sets are collections of sets {x 1,,x n}\{x_1, \ldots, x_n\}, and all sets are formed in this way. In order to found this conception on trees in a way that accepts the axiom of foundation, one must restrict to well-founded trees. A tree (pictured as a free category on a digraph, i.e., as a certain poset PP) is well-founded if every object of P opP^{op} is bounded above by a maximal element, or equivalently if there are no infinite chains x 0<x 1<x_0 \lt x_1 \lt \ldots in P opP^{op} starting from the root x 0x_0. (Chains starting from the root are also called branches.) See well-founded relation for other formulations of this definition (including those suitable for constructive mathematics; see pure set for details on this construction of the cumulative hierarchy, including using arbitrary trees for ill-founded sets.

The category of well-founded trees admits a (2-)universal description, as an initial algebra for a certain endofunctor on Cat. See well-founded forest? for details.

[To be continued]

Very nice! Is there a similar story worth telling for possibly infinite trees, corecursion, etc.

Toby: Well-founded trees (and pure sets) may be defined recursively; ill-founded trees (and pure sets) may be defined corecursively; there is stuff about this at pure set. (Note that even a well-founded tree may be infinite, as long as some vertex has infinitely many branches out of it.)

As relational structures

A rooted tree can be defined as a relational structure and as such serves as a useful model in the context of modal logics. In this form it consists of a set of nodes, vertices or whatever your preferred terminology is, and a binary relation, SS, on TT. These are to satisfy the following:

  • the set TT contains a unique element rr called the root, such that, for all tTt\in T, S *rtS^*r t holds, where S *S^* is the reflexive-transitive closure of SS;

  • if tTt\in T, and trt\neq r, then there is a unique tTt'\in T such that SttS t' t;

  • SS is acyclic, so for all tTt\in T, ¬S +tt\neg S^+ t t, where S +S^+ is the transitive closure of SS.

This last property, of course, implies that SS is irreflexive.

As polynomial endofunctors (after Kock)

A new way of thinking about (rooted, usually assumed finite) trees has been introduced by Joachim Kock.

Definition

A tree TT consists of a set T 0T_0 of edges, a set T 1T_1 of nodes, and a set T 2T_2 of input flags, all assumed finite, together with functions

T 0sT 2pT 1tT 0T_0 \stackrel{s}{\leftarrow} T_2 \stackrel{p}{\to} T_1 \stackrel{t}{\to} T_0

such that

  • tt is injective,
  • ss is injective and its image is complementary to a singleton {r}\{r\} (called the root), and
  • for all eT 0e \in T_0 there exists a natural number kk such that σ k(e)=r\sigma^k(e) = r, where σ:T 0T 0\sigma : T_0 \to T_0 is the “walk-to-root” function defined by et(p(s 1(e)))e \mapsto t(p(s^{-1}(e))) if ere \neq r, else rrr \mapsto r.

Some commentary is in order. The subscript 00 for edges and 11 for nodes is consonant with standard usage in string diagrams, where edges are labeled by 00-cells in a monoidal category and nodes by 11-cells. Each node is pictured as having a multiplicity of (and possibly zero) input edges and exactly one outgoing edge; the map t:T 1T 0t: T_1 \to T_0 maps a node to its outgoing edge. Only the root edge is not an input edge of any node, i.e., the unique inhabitant of the complement of im(s)im(s) is what we call the root rr. Now: the input “function” T 1T 0T_1 \to T_0 is actually a multivalued function, taking a node to the set of its input edges, and is therefore represented as a relation or span from T 0T_0 to T 1T_1. The domain of this relation T 2T_2 is the set of ordered pairs (e,v)(e, v) where eT 0e \in T_0 is an input edge of vT 1v \in T_1; this may be called a “flag” (thinking of a general flag as a chain of incidence relations, here a 1-step chain with ee input-incident to vv).

To each tree TT described in this form, there is an associated polynomial endofunctor p T:Set/T 0Set/T 0p_T: Set/T_0 \to Set/T_0 controlled by the data

T 0sT 2pT 1tT 0T_0 \stackrel{s}{\leftarrow} T_2 \stackrel{p}{\to} T_1 \stackrel{t}{\to} T_0

and defined by the composition

Set/T 0s *Set/T 2Π pSet/T 1Σ tSet/T 0Set/T_0 \stackrel{s^\ast}{\to} Set/T_2 \stackrel{\Pi_p}{\to} Set/T_1 \stackrel{\Sigma_t}{\to} Set/T_0

where as usual Σ ff *Π f\Sigma_f \dashv f^\ast \dashv \Pi_f. Notice that the functors on display preserve pullbacks, so p Tp_T preserves pullbacks.

There is a double category whose 00-cells are sets II, whose horizontal 11-cells are polynomial endofunctors p:Set/ISet/Jp: Set/I \to Set/J, whose vertical 11-cells are pullback functors f *:Set/ISet/If^\ast: Set/I \to Set/I' induced by functions f:IIf: I' \to I, and whose 22-cells are cartesian natural transformations of the form

Set/I p Set/J f * g * Set/I p Set/J\array{ Set/I & \stackrel{p}{\to} & Set/J \\ \mathllap{f^\ast} \downarrow & \swArrow & \downarrow \mathrlap{g^\ast} \\ Set/I' & \underset{p'}{\to} & Set/J' }

The category consisting of horizontal arrows and 2-cells between them is called the category of polynomial endofunctors, PolyEndPolyEnd. Kock defines a category of trees where objects are trees TT and whose morphisms are morphisms between the corresponding endofunctors p Tp_T as objects in PolyEndPolyEnd.

As Kock shows, this description of trees is well-adapted to the usual sorts of combinatorics that emerge in the study of operads, such as free operads.

References

Last revised on June 23, 2024 at 16:01:21. See the history of this page for a list of all contributions to it.